package com.demo.example.hot100;

public class MergeKLists {
    public static ListNode MergeKLists(ListNode[] lists){
        if(lists==null || lists.length==0){
            return null;
        }
        //仅有一个有序链表，就直接进行返回
        if(lists.length==1){
            return lists[0];
        }
        //链表的长度大于等于2
        ListNode res=MergeTwoLists(lists[0],lists[1]);
        for(int j=2;j< lists.length;j++){
            res=MergeTwoLists(res,lists[j]);
        }
        return res;
    }
    //写一个函数，用来合并两个有序链表
    public static ListNode MergeTwoLists(ListNode list1,ListNode list2){
        if(list1==null && list2!=null){
            return list2;
        }
        if(list2== null && list1!=null){
            return list1;
        }
        if(list1==null && list2==null){
            return null;
        }
        ListNode head=new ListNode(-1); //虚头部
        ListNode cur=head;
        while(list1!=null && list2!=null){
            int val1=list1.val;
            int val2=list2.val;
            int min=0;
            if(val1<val2){
                min=val1;
                list1=list1.next;
            }else{
                min=val2;
                list2=list2.next;
            }
            cur.next=new ListNode(min);
            cur=cur.next;
        }
        while(list1!=null){
            cur.next=new ListNode(list1.val);
            cur=cur.next;
            list1=list1.next;
        }
        while(list2!=null){
            cur.next=new ListNode(list2.val);
            cur=cur.next;
            list2=list2.next;
        }
        return head.next;
    }
}
